《数据结构》期末试卷A (精选03)
试卷信息：满分 100 分 | 考试时间 120 分钟 | 难度分布：基础 30% · 中等 45% · 提高 25%
一、判断分析题（判断下列描述是否正确，并给出分析理由，每小题3 分，共 15 分）。
1、使用带权有向连通图描述工程预计进度，缩短关键路径上的某个活动的时间，一定能缩短整个工程的工期。
查看答案与解析
答案：错误
解析：
本题考查 AOE 网（Activity On Edge Network）中关键路径的特性。
第一步：理解关键路径的定义
在 AOE 网中，从源点到汇点的路径长度最长的路径称为关键路径，关键路径上的活动称为关键活动。工程的工期由关键路径的长度决定。
第二步：分析缩短单个关键活动时间的影响
- 存在多条关键路径：如果一个工程存在多条关键路径，仅缩短其中一条路径上的某个关键活动时间，其他关键路径的长度并未改变，因此整个工程的工期不会缩短。
- 关键路径发生转移：即使只有一条关键路径，若过度缩短某个关键活动的时间，可能会导致原本的非关键路径演变为新的关键路径，此时工期的缩短量会受到新关键路径的限制。
结论：缩短关键路径上的某个活动时间，不一定能缩短整个工程的工期。
难度: ⭐⭐
考点: #关键路径 #AOE网 #工程工期
💡 学习锦囊
📖 相关公式与知识点:
- 事件最早发生时间 $ve(k)$：从源点到顶点 $v_k$ 的最长路径长度。
- 事件最迟发生时间 $vl(k)$：在不影响工程总工期的前提下，顶点 $v_k$ 允许发生的最迟时间。
- 关键活动：满足 $l(i) = e(i)$（即活动最早开始时间等于最迟开始时间）的活动。
思路分析
思考关键路径问题时，要时刻记住“木桶效应”。工程的完成时间取决于最慢的那条路径。如果有多条并行的最长路径，只优化其中一条是徒劳的。
🔄 举一反三
- 若关键路径上的活动时间增加，一定会导致工程工期延长吗？
查看练习答案与解析
答案：一定。
解析：关键路径是决定工程工期的最长路径。任何关键路径上的活动时间增加，都会导致该路径的长度增加。由于关键路径已经是最长路径，其长度增加必然导致整个工程的总工期延长。
2、顺序查找算法查找不成功的平均查找长度为 $(n+1)/2$。
查看答案与解析
答案：错误
解析：
本题考查顺序查找的平均查找长度（ASL）。
第一步：明确平均查找长度的计算公式
其中 $n$ 为查找表长度，$P_i$ 为查找第 $i$ 个记录的概率，$C_i$ 为找到第 $i$ 个记录所需的比较次数。
第二步：分析查找成功的 ASL
在等概率情况下，每个元素被查找的概率为 $P_i = \frac{1}{n}$。从前往后查找，找到第 $i$ 个元素需要比较 $i$ 次。
第三步：分析查找不成功的 ASL
当查找不成功时，说明关键字不在表中，必须将表中所有元素都比较一遍。
- 若不带哨兵：需要比较 $n$ 次。
- 若带哨兵：需要比较 $n+1$ 次。
结论：$(n+1)/2$ 是查找成功时的平均查找长度，而非查找不成功。
难度: ⭐
考点: #顺序查找 #平均查找长度 #ASL
💡 学习锦囊
📖 相关公式与知识点:
- 顺序查找成功：$ASL_{succ} = \frac{n+1}{2}$
- 顺序查找失败：$ASL_{unsucc} = n$（或 $n+1$）
- 带有哨兵的顺序查找可以省去判断下标是否越界的步骤，提高效率。
易错点
混淆查找成功与查找失败的比较次数。查找失败必须“走到最后”，无法提前结束。
🔄 举一反三
- 在长度为 $n$ 的有序顺序表上进行顺序查找，查找不成功的平均查找长度是多少？
查看练习答案与解析
答案：$\frac{n}{2} + \frac{n}{n+1}$（或约等于 $n/2$）
解析：由于表是有序的，当查找到某个元素大于（或小于）目标值时即可提前判定失败。等概率判定在 $n+1$ 个失败区间，平均比较次数约为 $n/2$。
3、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，序列 2，3，5，1，6，4是可能出现的出栈序列。
查看答案与解析
答案：错误
解析：
本题考查栈的“后进先出”（LIFO）特性。
模拟入栈与出栈过程：
- 序列首位出栈 2：说明此时 1, 2 已依次入栈，2 紧接着出栈。此时栈内状态：
[1]。 - 接着出栈 3：说明 3 入栈并立即出栈。此时栈内状态：
[1]。 - 接着出栈 5：说明 4, 5 依次入栈，5 紧接着出栈。此时栈内状态：
[1, 4]。 - 分析冲突：当前栈顶元素为 4。若要使序列中的 1 下一个出栈，根据栈的特性，必须先将栈顶的 4 弹出。
- 而给定的出栈序列中，1 却在 4 之前出栈，这违背了“后进先出”的原则。
结论：序列 2，3，5，1，6，4 是不可能出现的出栈序列。
难度: ⭐⭐
考点: #栈 #出栈序列 #LIFO
💡 学习锦囊
📖 相关公式与知识点:
- 栈是一种操作受限的线性表，只允许在栈顶进行插入和删除。
- $n$ 个元素通过一个初始为空的栈，能得到的合法出栈序列总数由卡特兰数（Catalan Number）决定：$C_n = \frac{1}{n+1} \binom{2n}{n}$。
思路分析
快速判断出栈序列是否合法的小技巧：在出栈序列中，对于任意出栈元素 $x$，在它之后出栈且比它先入栈的元素，必须是逆序排列的。
🔄 举一反三
- 若进栈序列为 A, B, C, D，下列哪个序列是不可能出现的出栈序列？ A. A, B, C, D B. D, C, B, A C. C, A, B, D D. C, B, A, D
查看练习答案与解析
答案：C
解析：- C 选项：先出 C，说明 A, B, C 已入栈。此时栈内为
[A, B]。 - 接下来要出 A，但栈顶是 B，必须先出 B 才能出 A。因此 C, A, B, D 违法。
- C 选项：先出 C，说明 A, B, C 已入栈。此时栈内为
4、数据结构的存储结构包括顺序存储、链式存储、哈希存储三种方式。
查看答案与解析
答案：错误
解析：
本题考查数据结构中存储结构（物理结构）的分类。
数据存储的四种基本方式：
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
- 链式存储：不要求物理位置相邻，通过指针指示逻辑关系。
- 索引存储：在存储元素的同时，建立附加的索引表（如关键字-地址映射）。
- 散列（哈希）存储：根据元素的关键字通过特定函数直接计算出存储地址。
结论：原描述遗漏了索引存储方式。
难度: ⭐
考点: #存储结构 #物理结构 #数据结构概念
💡 学习锦囊
📖 相关公式与知识点:
- 逻辑结构：面向问题，如集合、线性结构、树、图。
- 存储结构：面向计算机，是逻辑结构在计算机中的实现。
易错点
不要将“索引存储”与数据库索引的概念完全割裂，它们在底层都是通过额外的空间换取时间的策略。
🔄 举一反三
- 逻辑结构与存储结构的关系是？
查看练习答案与解析
答案：存储结构是逻辑结构在计算机存储器中的映射/实现。一种逻辑结构可以采用多种不同的存储结构来实现，而同一种存储结构也可以用来存储不同的逻辑结构。
5、设某棵二叉树的中序遍历序列为 ABCDE，先序遍历序列为 CABED，则后序遍历该二叉树得到序列为BADCE。
查看答案与解析
答案：错误
解析：
本题考查根据先序遍历和中序遍历序列还原二叉树并求解后序遍历。
第一步：确定根节点
先序序列 CABED 的第一个字符是 C，因此 C 为根节点。
第二步：划分左右子树
在中序序列 ABCDE 中找到根节点 C：
C左侧的AB构成左子树的中序序列。C右侧的DE构成右子树的中序序列。
第三步：递归构建子树
- 构建左子树：
- 左子树的中序为
AB。 - 对应在先序序列中，
A出现在B之前，故A为左子树的根。 - 中序中
B在A之后，说明B是A的右孩子。
- 左子树的中序为
- 构建右子树：
- 右子树的中序为
DE。 - 对应在先序序列中，
E出现在D之前，故E为右子树的根。 - 中序中
D在E之前，说明D是E的左孩子。
- 右子树的中序为
第四步：还原树形结构
C
/ \
A E
\ /
B D第五步：求后序遍历（左-右-根）
- 左子树后序：
B A - 右子树后序：
D E - 根节点：
C综合得到后序序列为：BADEC。
结论：后序序列应为 BADEC，原题中 BADCE 是错误的。
难度: ⭐⭐
考点: #二叉树遍历 #树的还原 #后序遍历
💡 学习锦囊
📖 相关公式与知识点:
- 先序：根 $\to$ 左 $\to$ 右
- 中序：左 $\to$ 根 $\to$ 右
- 后序：左 $\to$ 右 $\to$ 根
易错点
注意在确定右子树根节点时，先序序列中先出现的才是根。不要把中序的顺序直接当成根的顺序。
🔄 举一反三
- 已知一棵二叉树的先序遍历序列和后序遍历序列，能否唯一确定这棵二叉树？为什么？
查看练习答案与解析
答案：不能。
解析：先序和后序只能确定父子关系，无法确定是左孩子还是右孩子。例如：先序 AB，后序 BA，该树可以是一个根节点 A 带有左孩子 B，也可以是带有右孩子 B。
二、简答题（每小题 5 分，共 25 分）。
1、存在一个有向图 $G = (V,E)$，顶点数目为 $n$，该图的存储结构为邻接表，请回答下列问题： （1）求图 $G$ 中的边数的思路？
（2）如何判断图 $G$ 中的两个顶点 $i$ 和 $j$ 是否有边相连？
（3）如何计算图中顶点 $i$ 的入度？
查看答案与解析
答案：
(1) 求图 $G$ 中的边数： 在有向图的邻接表中，每个顶点 $v$ 关联一个单链表（边表），链表中的每个节点（弧节点）代表一条以该顶点为起点的有向弧。因此，求有向图的边数只需遍历邻接表中的所有顶点，统计它们关联的边表节点总数即可。
(2) 判断顶点 $i$ 和 $j$ 是否有边相连： 要判断是否存在从顶点 $i$ 到顶点 $j$ 的弧 $\langle i, j \rangle$：
- 找到顶点 $i$ 的表头结点。
- 沿着顶点 $i$ 对应的边表链表进行遍历。
- 若在链表中找到邻接顶点域为 $j$ 的节点，则说明有边相连；若遍历到链表末尾仍未找到，则说明无边相连。
(3) 计算顶点 $i$ 的入度： 顶点的入度是指以该顶点为终点的弧的数目。由于邻接表只存储了顶点的出边，计算入度需要遍历图中所有顶点的边表。
- 在遍历所有顶点的弧节点时，只要弧节点的邻接顶点域为 $i$，则计数器加 1。
- 遍历结束后，计数器的值即为顶点 $i$ 的入度。
难度: ⭐⭐
考点: #图 #邻接表 #入度与出度
💡 学习锦囊
📖 相关公式与知识点:
- 邻接表：顶点表（顺序存储）+ 边表（链式存储）。
- 对于有向图：
- 边表节点总数 = 边数 $|E|$
- 顶点 $i$ 的出度 = 顶点 $i$ 边表中的节点数
- 顶点 $i$ 的入度 = 所有边表中邻接点为 $i$ 的节点总数
思路分析
邻接表查找“出边”极其容易，时间复杂度为 $O(1)$ 至 $O(n)$；但查找“入边”需要全局扫描。如果题目中入度计算非常频繁，建议使用逆邻接表或十字链表存储。
🔄 举一反三
- 如果该邻接表表示的是无向图，求图 $G$ 的边数的思路是？
查看练习答案与解析
答案：遍历所有顶点的边表，统计弧节点总数，最后除以 2。
解析：在无向图的邻接表中，边 $(u, v)$ 会同时在 $u$ 的边表和 $v$ 的边表中各出现一次（即一个无向边对应两个弧节点），因此节点总数是实际边数的两倍。
2、假设存在一个函数定义：
double fun(double x, int n)
{
if (n==1)
return x;
return x * fun(x, n-1);
}（1）请问该函数 fun(x, n) 的功能是？
（2）函数调用 fun(2, 5) 的运算结果是？执行过程中发生了多少次递归调用？
（3）函数调用 fun(x, n) 最多发生了几次递归调用？
查看答案与解析
答案：
(1) 函数功能： 计算 $x$ 的 $n$ 次幂，即 $x^n$（要求 $n \geq 1$）。
(2) fun(2, 5) 的结果与调用次数：
- 运算结果：$2^5 = 32.0$。
- 递归调用次数：4 次。
- 过程：从首层
fun(2, 5)开始，分别触发了fun(2, 4)、fun(2, 3)、fun(2, 2)、fun(2, 1)的调用。其中fun(2, 1)触发了基准条件直接返回，因此属于第 4 次递归调用。
- 过程：从首层
(3) 最多发生递归调用的次数： 对于给定的正整数 $n$，最多发生 $n-1$ 次 递归调用。
难度: ⭐
考点: #递归 #时间复杂度 #递归深度
💡 学习锦囊
📖 相关公式与知识点:
- 递归算法的时间复杂度通常等于：递归调用次数 $\times$ 每次调用的时间复杂度。
- 空间复杂度通常取决于递归调用栈的最大深度。
易错点
数递归次数时容易把“首层调用”也算作递归。递归是指“自己调用自己”，首次进入主函数不计入递归调用次数。
🔄 举一反三
- 若将基准条件改为
if (n==0) return 1;，则fun(2, 5)的递归调用次数是？查看练习答案与解析
答案：5 次。
解析：递归路径为 $5 \to 4 \to 3 \to 2 \to 1 \to 0$，共递推 5 次才到达基准条件。
3、在以下三种存储结构中，哪个最适合用作链栈？并说明理由。 （1）带头节点的单链表 （2）不带头节点的循环单链表
（3）带头节点的双链表
查看答案与解析
答案：
最适合的是：（1）带头结点的单链表。
理由：
- 栈的操作特性：栈是仅允许在栈顶进行插入（入栈）和删除（出栈）的线性表，遵循“后进先出”（LIFO）原则。
- 效率与简单性：使用带头结点的单链表，我们可以将头结点之后的位置作为栈顶。入栈（在头结点后插入）和出栈（删除头结点后的首元素）操作都只需要修改
head->next指针，时间复杂度为 $O(1)$，逻辑最简单。 - 结构对比：
- （2）不带头结点的循环单链表：为了方便在头部操作，需要额外维护尾指针，且在处理空表时逻辑比带头结点更繁琐。
- （3）带头结点的双链表：虽然操作也是 $O(1)$，但双链表每个节点多了一个前驱指针
prior。栈的操作并不需要向前遍历，双向指针只会白白浪费内存，且维护指针的代数开销更大。
难度: ⭐⭐
考点: #栈 #链栈 #存储结构设计
💡 学习锦囊
📖 相关公式与知识点:
- 带头结点的链栈：
- 空栈判定：
S->next == NULL - 入栈（头插法）：
p->next = S->next; S->next = p; - 出栈：
p = S->next; S->next = p->next; free(p);
- 空栈判定：
思路分析
设计数据结构时应遵循“够用就好”原则。栈不需要随机访问，不需要双向遍历，因此单链表是最优、最经济的选择。
🔄 举一反三
- 如果需要设计一个链式队列（先进先出），上述三种结构中哪种更优？
查看练习答案与解析
答案：带有头结点且具备尾指针的单链表，或带头结点的双链表。
解析：队列需要在头部删除（出队），在尾部插入（入队），必须保证头尾操作均为 $O(1)$。
4、特殊矩阵和稀疏矩阵两种矩阵压缩方法，哪一种方法失去随机存取功能？请解释原因。
查看答案与解析
答案：
失去随机存取功能的是：稀疏矩阵的压缩存储。
原因：
- 随机存取是指在 $O(1)$ 的时间复杂度内，根据行、列下标 $(i, j)$ 直接定位并访问到对应的元素。
- 特殊矩阵（如对称矩阵、对角矩阵）：元素分布是有规律的。压缩后虽然存入了一维数组，但可以通过数学公式（例如对称矩阵映射 $k = \frac{i(i-1)}{2} + j - 1$）直接计算出对应的数组下标，因此保留了随机存取功能。
- 稀疏矩阵（如采用三元组或十字链表）：非零元素分布毫无规律。要查找指定位置 $(i, j)$ 的值，必须遍历整个三元组表逐个比对行号列号，或者沿着链表指针顺次查找。存取时间与非零元素个数相关，无法直接定位，因此失去了随机存取功能。
难度: ⭐⭐
考点: #矩阵压缩 #随机存取 #特殊矩阵
💡 学习锦囊
📖 相关公式与知识点:
- 三元组表：存储
(row, col, value)的顺序存储结构。 - 十字链表：包含行指针数组和列指针数组的链式存储结构。
易错点
不要认为所有“压缩”都会导致无法随机存取。关键在于元素的逻辑位置与物理存储地址之间是否存在固定的数学函数关系。
🔄 举一反三
- 对于一个 $n \times n$ 的对称矩阵 $A$，按行优先原则将下三角元素压缩存储到一维数组 $B$ 中，则元素 $a_{i,j} (i \geq j)$ 在 $B$ 中的下标（从 0 开始）为？
查看练习答案与解析
答案：$\frac{i(i+1)}{2} + j$（若矩阵下标从 0 开始）或 $\frac{i(i-1)}{2} + j - 1$（若矩阵下标从 1 开始）。
解析：前 $i$ 行共有 $1+2+...+i = \frac{i(i+1)}{2}$ 个元素，加上当前行的 $j$ 个偏移量。
5、假设有如下算法，该算法的目标是删除顺序表 $L$ 中的第一个元素，指出其中的错误。
void del(SqList L)
{
int i;
for (i = 1; i < L.length; i++)
L.data[i-1] = L.data[i];
}查看答案与解析
答案：
该算法存在以下三个致命错误：
- 参数传递方式错误（传值调用）： 函数的形参为
SqList L。在 C/C++ 中，这是值传递，函数内部操作的只是外部实参的一个局部副本。当函数退出时，这个副本被销毁，外部真正的顺序表 $L$ 没有发生任何改变。 - 未更新顺序表长度： 循环体
L.data[i-1] = L.data[i]成功将第 2 个至最后一个元素向前覆盖移动了一位，但算法结束前没有将表长进行递减。这会导致原顺序表的最后一个数据残留，且表长仍为原值。 - 缺乏空表校验（健壮性差）： 若传入的顺序表为空（
L.length == 0），强行执行删除是不合法的，应当在循环前加入边界判断。
难度: ⭐⭐
考点: #顺序表 #参数传递 #代码纠错
💡 学习锦囊
📖 相关公式与知识点:
- 修改外部变量时，必须传递指针（
SqList *L）或引用（SqList &L）。 - 顺序表删除操作的时间复杂度主要消耗在元素的移动上，均摊复杂度为 $O(n)$。
思路分析
排查算法题时，不仅要看“数据有没有移对”，还要看“长度改没改”、“改动有没有生效”以及“空表会不会崩”。
🔄 举一反三
- 请写出上述算法修正后的正确代码（使用 C++ 引用方式）。
查看练习答案与解析
答案：
cppbool del(SqList &L) { if (L.length == 0) return false; // 校验空表 for (int i = 1; i < L.length; i++) { L.data[i-1] = L.data[i]; } L.length--; // 更新表长 return true; }
三、应用分析题(每小题 8 分，共 40 分)。
1、存在一个整数序列 $\{15, 5, 16, 2, 25, 8, 20, 9, 18, 12\}$，需要对该序列进行升序排序，如果采用二路归并排序法，请写出每一趟排序后的结果。
查看答案与解析
答案：
二路归并排序的核心思想是将序列两两配对合并。初始状态下，每个元素视为一个独立的有序子表。
初始状态：
$[15], [5], [16], [2], [25], [8], [20], [9], [18], [12]$第一趟归并（子表长度为 2）：
对相邻的两个长度为 1 的子表进行合并。
结果：$[5, 15], [2, 16], [8, 25], [9, 20], [12, 18]$第二趟归并（子表长度为 4）：
对相邻的两个长度为 2 的子表进行合并。
结果：$[2, 5, 15, 16], [8, 9, 20, 25], [12, 18]$第三趟归并（子表长度为 8）：
对相邻的两个长度为 4 的子表进行合并（末尾不足 4 的直接合并）。
结果：$[2, 5, 8, 9, 15, 16, 20, 25], [12, 18]$第四趟归并（子表长度为 16）：
最后一次合并，得到完全有序的序列。
结果：$[2, 5, 8, 9, 12, 15, 16, 18, 20, 25]$
难度: ⭐⭐
考点: #归并排序 #分治法 #排序算法过程
💡 学习锦囊
📖 相关公式与知识点:
- 时间复杂度：最好、最坏、平均均为 $O(n \log_2 n)$。
- 空间复杂度：$O(n)$（需要辅助数组）。
- 稳定性：是一种稳定的排序算法。
思路分析
做归并排序的过程题时，要严格按照子表长度翻倍（1 -> 2 -> 4 -> 8...）的规律进行两两合并，注意处理末尾元素不够合并的情况。
🔄 举一反三
- 归并排序在处理超大数据量且内存不足以一次性装下时，通常采用什么策略？
查看练习答案与解析
答案：外部排序（External Sorting）。
解析：将数据分块读入内存排序，存回外存，最后使用多路平衡归并技术进行外排序。
2、假设有一个带权无向图（如下图所示），以顶点 0 作为起点构造最小生成树，请写出普里姆算法的执行过程。如果使用克鲁斯卡尔算法构造出的最小生成树，请写出执行过程。
查看答案与解析
答案：
根据题图，图的顶点集合为 $V = \{0, 1, 2, 3, 4, 5\}$，边与权值如下： $(0,1):1, (0,3):2, (1,2):3, (4,5):4, (0,2):5, (2,5):6, (1,4):7, (3,5):8$。
(1) 普里姆 (Prim) 算法执行过程（从顶点 0 开始）： Prim 算法通过不断吸收“离当前生成树最近的顶点”来扩展。
- 初始状态：已选顶点集 $U = \{0\}$。
- 第 1 步：候选边为 $(0,1):1, (0,2):5, (0,3):2$。选出最小边 $(0,1):1$。$U = \{0, 1\}$。
- 第 2 步：候选边增入 $(1,2):3, (1,4):7$。当前候选最小边为 $(0,3):2$。$U = \{0, 1, 3\}$。
- 第 3 步：候选边增入 $(3,5):8$。当前候选最小边为 $(1,2):3$。$U = \{0, 1, 2, 3\}$。
- 第 4 步：候选边增入 $(2,5):6$。当前候选最小边为 $(4,5)$ 与 $(2,5)$ 中的 $(2,5):6$（注意：$(0,2)$ 构成回路舍弃）。$U = \{0, 1, 2, 3, 5\}$。
- 第 5 步：候选边增入 $(4,5):4$。选出最小边 $(4,5):4$。$U = \{0, 1, 2, 3, 5, 4\}$。
生成树的边为：$(0,1), (0,3), (1,2), (2,5), (4,5)$。总权值为 $1+2+3+6+4 = 16$。
(2) 克鲁斯卡尔 (Kruskal) 算法执行过程： Kruskal 算法通过按权值从小到大依次选择边，只要不构成回路即可。
- 将所有边按权值升序排列： $(0,1):1, (0,3):2, (1,2):3, (4,5):4, (0,2):5, (2,5):6, (1,4):7, (3,5):8$。
- 依次选边：
- 选 $(0,1):1$，无回路，加入。
- 选 $(0,3):2$，无回路，加入。
- 选 $(1,2):3$，无回路，加入。
- 选 $(4,5):4$，无回路，加入。
- 选 $(0,2):5$，构成回路 $0-1-2-0$，舍弃。
- 选 $(2,5):6$，无回路，加入。
- 此时已选出 $n-1=5$ 条边，算法结束。
生成树的边同样为：$(0,1), (0,3), (1,2), (4,5), (2,5)$。总权值为 $16$。
难度: ⭐⭐⭐
考点: #最小生成树 #Prim算法 #Kruskal算法
💡 学习锦囊
📖 相关公式与知识点:
- Prim 算法：适用于稠密图，时间复杂度为 $O(|V|^2)$。
- Kruskal 算法：适用于稀疏图，时间复杂度为 $O(|E| \log_2 |E|)$，常用并查集判断回路。
易错点
在 Prim 的候选边选择中，一定要注意过滤掉已经并入 $U$ 集合的顶点之间产生的边（防止产生闭环）。
🔄 举一反三
- 最小生成树的形态是否唯一？
查看练习答案与解析
答案：不一定唯一。
解析：当图中存在权值相等的边时，可能构造出多棵不同的最小生成树；但最小生成树的权值之和必然是唯一且最小的。
3、有一棵二叉排序树 T，该二叉树的先序遍历结果为：$(12,5,2,8,6,10,16,15,18,20)$。请解答： （1）请构造二叉树T，并画出树形结构。
（2）请写出该二叉树的中序遍历结果。 （3）求在等概率下的查找成功和不成功情况下的平均查找长度。
查看答案与解析
答案：
(1) 构造二叉树 T 并画出树形结构： 二叉排序树（BST）的先序遍历实际上就是按照元素的插入顺序进行构建。
- 根为 12。
- 5 小于 12，作为 12 的左子树；16 大于 12，作为 12 的右子树。
- 依此类推，构建出的二叉树结构如下：
12
/ \
5 16
/ \ / \
2 8 15 18
/ \ \
6 10 20(2) 中序遍历结果： 二叉排序树的中序遍历必然是有序递增的。 中序遍历结果：$(2, 5, 6, 8, 10, 12, 15, 16, 18, 20)$
(3) 平均查找长度 (ASL)：
查找成功 $ASL_{succ}$：
节点层数 节点 比较次数 第 1 层 12 $1 \times 1 = 1$ 第 2 层 5, 16 $2 \times 2 = 4$ 第 3 层 2, 8, 15, 18 $4 \times 3 = 12$ 第 4 层 6, 10, 20 $3 \times 4 = 12$ 总共 10 个节点。
$$ASL_{succ} = \frac{1 + 4 + 12 + 12}{10} = \frac{29}{10} = 2.9$$查找不成功 $ASL_{unsucc}$（对应 11 个空指针位置）： 查找失败的比较次数等于其父节点的层数。
- 2 (第 3 层) 下有 2 个空指针：$2 \times 3 = 6$
- 15 (第 3 层) 下有 2 个空指针：$2 \times 3 = 6$
- 18 (第 3 层) 下有 1 个空指针：$1 \times 3 = 3$
- 6 (第 4 层) 下有 2 个空指针：$2 \times 4 = 8$
- 10 (第 4 层) 下有 2 个空指针：$2 \times 4 = 8$
- 20 (第 4 层) 下有 2 个空指针：$2 \times 4 = 8$
$$ASL_{unsucc} = \frac{6 + 6 + 3 + 8 + 8 + 8}{11} = \frac{39}{11} \approx 3.55$$
难度: ⭐⭐⭐
考点: #二叉排序树 #ASL #树的构建
💡 学习锦囊
📖 相关公式与知识点:
- BST 性质：左子树 < 根 < 右子树。
- 查找失败的判定位置是叶子结点的虚构子节点（失败结点）。
易错点
求不成功 ASL 时，分母必须是失败结点的个数，即 $n+1$（空指针总数），千万别误用节点数 $n$ 作为分母。
🔄 举一反三
- 若要使上述 BST 变为平衡二叉树，可以通过什么操作？
查看练习答案与解析
答案：通过单旋（LL、RR）或双旋（LR、RL）进行调整。
解析：计算每个节点的平衡因子，从失衡点开始旋转重构。
4、假设存在一个整数序列 $\{4, 5, 7, 2, 1, 3, 6\}$，以该序列作为输入，构建一棵空平衡二叉树，请写出该平衡二叉树的构建过程。请画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出调整类型。
查看答案与解析
答案：
平衡二叉树（AVL 树）要求任意节点的左右子树高度差的绝对值 $\leq 1$。
插入 4, 5, 7：
- 插入 4, 5 无异常。
- 插入 7 后，节点 4 的平衡因子变为 -2，发生 RR 型失衡。
- 调整：对节点 4 进行左单旋。
- 结果：
5 / \ 4 7
插入 2, 1：
- 插入 2 无异常。
- 插入 1 后，节点 4 的平衡因子变为 2，发生 LL 型失衡。
- 调整：对节点 4 进行右单旋。
- 结果：
5 / \ 2 7 / \ 1 4
插入 3：
- 插入 3 后，根节点 5 的平衡因子变为 2，左子树 2 的平衡因子为 -1，发生 LR 型失衡。
- 调整：先对 2 进行左旋，再对 5 进行右旋（先左后右双旋）。
- 结果：
4 / \ 2 5 / \ \ 1 3 7
插入 6：
- 插入 6 后，节点 5 的平衡因子变为 -2，发生 RL 型失衡。
- 调整：先对 7 进行右旋，再对 5 进行左旋（先右后左双旋）。
- 结果（最终形态）：
4 / \ 2 6 / \ / \ 1 3 5 7
难度: ⭐⭐⭐
考点: #AVL树 #平衡因子 #树的旋转
💡 学习锦囊
📖 相关公式与知识点:
- 平衡因子 (BF) = 左子树高度 - 右子树高度。
- 四种旋转：LL（右旋）、RR（左旋）、LR（先左后右）、RL（先右后左）。
思路分析
每次插入新节点后，要从下往上依次检查平衡因子。一旦发现失衡点（绝对值 $>1$），立即对该失衡点执行旋转，不要拖延。
学习建议
对于复杂的平衡旋转，强烈建议手动在纸上画出节点的移动轨迹，或者利用在线数据结构可视化工具（如 VisuAlgo）动态观察 LL/RR/LR/RL 的旋转细节。
🔄 举一反三
- 在平衡二叉树中删除一个节点后，是否一定会导致树失衡？
查看练习答案与解析
答案：不一定。
解析：只有当被删除节点属于较矮子树或导致平衡因子越界时才需要旋转调整。
5、设有一组关键字 $\{32, 13, 49, 24, 38, 21, 4, 12\}$，其哈希函数为：$H(key) = key \% 7$，采用开放地址法的线性探查法解决冲突，试在 $0 \sim 9$ 的哈希地址空间中对该关键字序列构造哈希表，并求等概率下查找成功和查找失败的平均查找长度。
查看答案与解析
答案：
第一步：构造哈希表
利用 $H(key) = key \% 7$ 计算初始位置，若有冲突则进行线性探查（下标依次 +1）。
- 32: $32 \% 7 = 4$。无冲突，存入位置 4。
- 13: $13 \% 7 = 6$。无冲突，存入位置 6。
- 49: $49 \% 7 = 0$。无冲突，存入位置 0。
- 24: $24 \% 7 = 3$。无冲突，存入位置 3。
- 38: $38 \% 7 = 3$。冲突（3已被占），探查位置 4（占）、5（空），存入位置 5。
- 21: $21 \% 7 = 0$。冲突（0已被占），探查位置 1（空），存入位置 1。
- 4: $4 \% 7 = 4$。冲突（4、5、6均被占），探查位置 7（空），存入位置 7。
- 12: $12 \% 7 = 5$。冲突（5、6、7均被占），探查位置 8（空），存入位置 8。
哈希表最终状态：
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 49 | 21 | 24 | 32 | 38 | 13 | 4 | 12 |
第二步：计算平均查找长度 (ASL)
查找成功 $ASL_{succ}$：
关键字 初始地址 实际地址 比较次数 49 0 0 1 21 0 1 2 24 3 3 1 32 4 4 1 38 3 5 3 13 6 6 1 4 4 7 4 12 5 8 4 $$ASL_{succ} = \frac{1 + 2 + 1 + 1 + 3 + 1 + 4 + 4}{8} = \frac{17}{8} = 2.125$$查找失败 $ASL_{unsucc}$（对哈希映射区间 $0 \sim 6$ 依次向后比对直到遇到空位）：
- $H=0$: 探查 0, 1, 2（遇到空），比较 3 次。
- $H=1$: 探查 1, 2，比较 2 次。
- $H=2$: 探查 2，比较 1 次。
- $H=3$: 探查 3, 4, 5, 6, 7, 8, 9，比较 7 次。
- $H=4$: 探查 4, 5, 6, 7, 8, 9，比较 6 次。
- $H=5$: 探查 5, 6, 7, 8, 9，比较 5 次。
- $H=6$: 探查 6, 7, 8, 9，比较 4 次。
$$ASL_{unsucc} = \frac{3 + 2 + 1 + 7 + 6 + 5 + 4}{7} = \frac{28}{7} = 4.0$$
难度: ⭐⭐⭐
考点: #哈希表 #开放地址法 #线性探测 #ASL
💡 学习锦囊
📖 相关公式与知识点:
- 冲突处理：$d_i = (d_0 + i) \% m$。
- 装填因子 $\alpha = n/m$。
易错点
失败 ASL 的分母是哈希函数的映射范围大小（本题为 7），绝不是哈希表的整体长度 10。
🔄 举一反三
- 解决哈希冲突的方法除了开放地址法，还有哪些常用策略？
查看练习答案与解析
答案：链地址法（拉链法）、再哈希法、建立公共溢出区。
解析：拉链法在插入与删除上更灵活，常用于解决空间浪费问题。
四、程序设计题(每小题10 分，共 20 分)。
1、假设二叉树采用二叉链存储结构，设计一个算法求二叉树 $b$ 中度为 2 的结点个数，其结点类型如下：
typedef struct node {
char data;
struct node *lchild, *rchild;
} BTNode;请给出递归模型的设计，并写出函数实现代码。
查看答案与解析
答案：
递归模型设计： 设 $f(b)$ 为以 $b$ 为根的二叉树中度为 2 的结点个数：
- 基准条件：若二叉树为空，则度为 2 的结点数为 0。$$f(b) = 0 \quad (\text{当 } b == \text{NULL})$$
- 递推关系：
- 若根节点 $b$ 的左右孩子均不为空（度为 2）：$$f(b) = 1 + f(b\rightarrow\text{lchild}) + f(b\rightarrow\text{rchild})$$
- 否则（度为 0 或 1）：$$f(b) = f(b\rightarrow\text{lchild}) + f(b\rightarrow\text{rchild})$$
- 若根节点 $b$ 的左右孩子均不为空（度为 2）：
函数实现代码 (C语言)：
int countDegreeTwo(BTNode *b) {
if (b == NULL) {
return 0; // 空树
}
// 判定度为 2 的结点
if (b->lchild != NULL && b->rchild != NULL) {
return 1 + countDegreeTwo(b->lchild) + countDegreeTwo(b->rchild);
} else {
return countDegreeTwo(b->lchild) + countDegreeTwo(b->rchild);
}
}难度: ⭐⭐
考点: #二叉树 #递归算法 #度数计算
💡 学习锦囊
📖 相关公式与知识点:
- 二叉树的基本性质：若度为 0、1、2 的结点数分别为 $n_0, n_1, n_2$，则总结点数 $n = n_0 + n_1 + n_2$，且分支数 $B = n - 1 = n_1 + 2n_2 \implies n_0 = n_2 + 1$。
思路分析
递归遍历二叉树是解决树问题的万能钥匙。核心在于明确“当前节点要做什么”（判断度）以及“如何整合子树的结果”（左右子树累加）。
🔄 举一反三
- 设计算法求二叉树中叶子结点（度为 0）的个数。
查看练习答案与解析
答案：
cppint countLeaf(BTNode *b) { if (b == NULL) return 0; if (b->lchild == NULL && b->rchild == NULL) return 1; return countLeaf(b->lchild) + countLeaf(b->rchild); }
2、假设存在一个带头结点的单链表 $L$，每个节点中存储一个整数，请设计一个算法实现：删除 $L$ 中结点值最小的所有结点（可能有多个结点值最小的结点）。
函数声明参考：void DelMinNodes(LinkList *L);
查看答案与解析
答案：
算法设计思路： 由于链表无序且可能存在多个最小值，算法分为两步：
- 第一趟遍历：从头到尾扫描链表，找出数据域的全局最小值
min_val。 - 第二趟遍历：利用双指针（
pre和p），依次检查每个节点的数据域。若p->data == min_val，则将其删除并释放空间；否则指针同步后移。
函数实现代码 (C语言)：
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
void DelMinNodes(LinkList *L) {
if (L == NULL || (*L)->next == NULL) {
return; // 链表为空或只有头结点
}
// 第一步：寻找最小值
LNode *p = (*L)->next;
int min_val = p->data;
while (p != NULL) {
if (p->data < min_val) {
min_val = p->data;
}
p = p->next;
}
// 第二步：删除所有等于最小值的节点
LNode *pre = *L;
p = (*L)->next;
while (p != NULL) {
if (p->data == min_val) {
pre->next = p->next; // 断开链接
free(p); // 释放内存
p = pre->next; // 继续检查新后继
} else {
pre = p;
p = p->next; // 双指针同步后移
}
}
}难度: ⭐⭐⭐
考点: #单链表 #链表删除 #双指针
💡 学习锦囊
📖 相关公式与知识点:
- 单链表删除节点的核心逻辑：
pre->next = p->next; free(p); - 注意：删除操作完成后，当前指针
p已失效，必须通过pre->next重新赋值。
易错点
如果遗漏了 free(p) 会造成内存泄漏；如果删除了 p 却没有重新定位 p 而是直接 p = p->next，会导致非法内存访问崩溃。
学习建议
在手写链表算法时，强烈建议在草稿纸上画出链表节点以及指针（如 pre, p）的指向变化，特别是在发生“删除”动作的前后，能够大幅降低指针悬挂和越界错误的发生率。
🔄 举一反三
- 设计算法删除带头结点的单链表中所有值为 $x$ 的结点。
查看练习答案与解析
答案：
cppvoid DelX(LinkList &L, int x) { LNode *pre = L, *p = L->next; while (p != NULL) { if (p->data == x) { pre->next = p->next; free(p); p = pre->next; } else { pre = p; p = p->next; } } }